2829-k-avoiding 数组的最小总和

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给你两个整数 n 和 k 。

对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。

返回长度为 n 的 k-avoiding 数组的可能的最小总和。

示例 1：

**输入：** n = 5, k = 4
**输出：** 18
**解释：** 设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。
可以证明不存在总和小于 18 的 k-avoiding 数组。

示例 2：

**输入：** n = 2, k = 6
**输出：** 3
**解释：** 可以构造数组 [1,2] ，其元素总和为 3 。
可以证明不存在总和小于 3 的 k-avoiding 数组。

提示：

  • 1 <= n, k <= 50

请看 视频讲解 第二题。

对于 [1,k-1] 内的数字：

  • 1 和 k-1 只能选其中一个；
  • 2 和 k-2 只能选其中一个；
  • 3 和 k-3 只能选其中一个；
  • ……
  • 一直到 \left\lfloor\dfrac{k}{2}\right\rfloor，无论 k 是奇数还是偶数，它都可以选。

设 m=\min\left(\left\lfloor\dfrac{k}{2}\right\rfloor, n\right)，那么答案的第一段是从 1 到 m，元素和为

\dfrac{m(m+1)}{2}

此时还剩下 n-m 个数，只能从 k 开始往后选，那么答案的第二段是从 k 到 k+n-m-1，元素和为

\dfrac{(2k+n-m-1)(n-m)}{2}

所以答案为

\dfrac{m(m+1) + (2k+n-m-1)(n-m)}{2}

[sol-Python3]
1
2
3
4
class Solution:
    def minimumSum(self, n: int, k: int) -> int:
        m = min(k // 2, n)
        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2
[sol-Java]
1
2
3
4
5
6
class Solution {
    public int minimumSum(int n, int k) {
        int m = Math.min(k / 2, n);
        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) / 2;
    }
}
[sol-C++]
1
2
3
4
5
6
7
class Solution {
public:
    int minimumSum(int n, int k) {
        int m = min(k / 2, n);
        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) / 2;
    }
};
[sol-Go]
1
2
3
4
5
6
func minimumSum(n, k int) int {
	m := min(k/2, n)
	return (m*(m+1) + (k*2+n-m-1)*(n-m)) / 2
}

func min(a, b int) int { if b < a { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(1)。
  • 空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。
 Comments
On this page
2829-k-avoiding 数组的最小总和